package exp5;

public class QuadraticProbingHashTable3<AnyType> {
    public static void main(String[] args) {
        QuadraticProbingHashTable3<Integer> H = new QuadraticProbingHashTable3<>();
        H.insert(4371);
        H.insert(1223);
        H.insert(6173);
        H.insert(4199);
        H.insert(4344);
        H.insert(9679);
        H.insert(1989);
        for (int i = 0; i < H.array.length; i++)
            if (H.array[i] != null)
                System.out.println("{" + i + ":" + H.array[i].element + "}");
    }

    public QuadraticProbingHashTable3() {
        this(DEFAULT_TABLE_SIZE);
    }

    public QuadraticProbingHashTable3(int size) {
        allocateArray(size);
        makeEmpty();
    }

    public boolean insert(AnyType x) {
        int currentPos = findPos(x);
        if (isActive(currentPos))
            return false;
        array[currentPos] = new HashEntry<>(x);
        theSize++;
        if (++occupied > array.length / 2)
            rehash();
        return true;
    }

    private void rehash() {
        HashEntry<AnyType>[] oldArray = array;
        allocateArray(2 * oldArray.length);
        occupied = 0;
        theSize = 0;
        for (HashEntry<AnyType> entry : oldArray)
            if (entry != null && entry.isActive)
                insert(entry.element);
    }

    private int findPos(AnyType x) {
        int offset = 1;
        int currentPos = myhash(x);
        int hash2 = myhash2(x);
        while (array[currentPos] != null &&
                !array[currentPos].element.equals(x)) {
            currentPos += hash2;
            if (currentPos >= array.length)
                currentPos -= array.length;
        }
        return currentPos;
    }

    public boolean remove(AnyType x) {
        int currentPos = findPos(x);
        if (isActive(currentPos)) {
            array[currentPos].isActive = false;
            theSize--;
            return true;
        } else
            return false;
    }

    public int size() {
        return theSize;
    }

    public int capacity() {
        return array.length;
    }

    public boolean contains(AnyType x) {
        int currentPos = findPos(x);
        return isActive(currentPos);
    }

    private boolean isActive(int currentPos) {
        return array[currentPos] != null && array[currentPos].isActive;
    }

    public void makeEmpty() {
        occupied = 0;
        for (int i = 0; i < array.length; i++)
            array[i] = null;
    }

    private int myhash(AnyType x) {
        int hashVal = x.hashCode();
        hashVal %= array.length;
        if (hashVal < 0)
            hashVal += array.length;
        return hashVal;
    }

    private static class HashEntry<AnyType> {
        public AnyType element;
        public boolean isActive;

        public HashEntry(AnyType e) {
            this(e, true);
        }

        public HashEntry(AnyType e, boolean i) {
            element = e;
            isActive = i;
        }
    }

    private static final int DEFAULT_TABLE_SIZE = 11;
    private HashEntry<AnyType>[] array;
    private int occupied;
    private int theSize;

    private void allocateArray(int arraySize) {
        array = new HashEntry[nextPrime(arraySize)];
    }

    private static int nextPrime(int n) {
        if (n % 2 == 0)
            n++;
        for (; !isPrime(n); n += 2)
            ;
        return n;
    }

    private static boolean isPrime(int n) {
        if (n == 2 || n == 3)
            return true;
        if (n == 1 || n % 2 == 0)
            return false;
        for (int i = 3; i * i <= n; i += 2)
            if (n % i == 0)
                return false;
        return true;
    }

    private int myhash2(AnyType x) {
        int hashVal = x.hashCode();
        hashVal = 7 - (hashVal % 7);
        return hashVal;
    }
}